For a network system that centrally controls designing and configuration of communication routes, there is a technique to receive a request for route construction (which may also be referred to as “route search”) from an operator, and to, in response to the request, search for a communication route from a start point node to an end point node that satisfies the quality requested by the operator.
Dijkstra's algorithm is known as a method of implementing a search for a route that satisfies conditions such as a hop length. Dijkstra's algorithm uses a metric value defined for each link and identifies a single route that has the smallest sum of metric values among routes. A “metric value” may also be referred to as an “index” or a “cost value”.
A metric value is a route length (which may also be referred to as “hop length” or “the number of hops”), for example. “Hop length” is the number of nodes that are passed from a start point node to an end point node.
There is a depth-first search method as a method of extracting a route candidate. The “depth-first search method” generates a search tree having a start point node as a root node (which may also be referred to a “root”) and sequentially search nodes down to a predetermined hop length (or a depth).
As examples of prior-art, are known Japanese Laid-open Patent Publication Nos. 7-162415, 6-97964 and 2008-54211 and the like.